package com.jiang.专题.动态规划.Q983;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/09 18:21
 */
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int len = days.length;
        int[] dp = new int[days[len - 1] + 1]; // dp[i] 表示第i天之前的最低消费
        for (int i = 1, j = 0; i <= days[len - 1]; i++) {
            dp[i] = dp[i - 1]; // 存储前一天的消费
            // 如果第i天是旅游日期，那么就根据三种票价算最低消费；如果不是旅游日期，那我们可以贪心地选择不买
            if (i == days[j]) {
                dp[i] = dp[i - 1] + costs[0];
                dp[i] = Math.min(dp[i], dp[Math.max(0, i - 7)] + costs[1]); // 当i - 7 小于0取0
                dp[i] = Math.min(dp[i], dp[Math.max(0, i - 30)] + costs[2]);
                j++;
            }
        }
        return dp[days[len - 1]];
    }
}
